package codetop.microsoft.T222;

import util.TreeNode;

/**
 * @Author: 18362
 * @Create: 2022-09-11 16:03:59 星期日
 */
class Solution {

    public int countNodes(TreeNode root) {
        if (root == null)
            return 0;
        int leftHeight = getHeight(root.left), rightHeight = getHeight(root.right);
        if (leftHeight == rightHeight)
            return (1 << leftHeight) + countNodes(root.right);
        return (1 << rightHeight) + countNodes(root.left);
    }

    private int getHeight(TreeNode root) {
        if (root == null)
            return 0;
        return Math.max(getHeight(root.left), getHeight(root.right)) + 1;
    }
}